/**最长的回文子序列 ---最长的长度是多少 【不连续】
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
 */

/**
 * dp[i][j] 表示 s[i...j] 的最长回文子序列的长度
 * 1. s[i]==s[j]
 * dp[i][j] = dp[i+1][j-1]+2; 内部也是最长回文
 * 2. s[i]!=s[j] 构不成回文， 
 * dp[i][j] = max(dp[i+1][j]--去掉左边元素, dp[i][j-1]---去掉右边元素)
 * 【遍历顺序】 [i+1]从尾部开始， j i+1开始
 * 【初始化】 每个元素本身都是回文，所以dp[i][i] = 1;
 */
var longestPalindromeSubseq = function(s) {
  const m = s.length;
  const dp =Array(m).fill().map(() => Array(m).fill(0));
  for(let i=m-1;i>=0;i--) {
    for(let j=i;j<m;j++) { //j=i+1因为 ii已经初始化了
      if(s[i]==s[j]) {
        dp[i][j] = dp[i+1][j-1]+2;
      }else {
        dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
      }
    }
  }
  return dp[0][m-1];
};

const s = "bbbab";
console.log('最长回文子序列',longestPalindromeSubseq(s));//4